﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//加油站
class Solution
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int n = gas.size();
        // 依次枚举所有的起点
        for (int i = 0; i < n; i++)
        {
            int res = 0;//净收益
            int step = 0;//走的步数
            for (; step < n; step++)
            {
                // 求出⾛ step 步之后的下标
                int index = (i + step) % n;
                res = res + gas[index] - cost[index];
                if (res < 0)
                    break;
            }
            if (res >= 0)  return i;
            // 当从 i 位置出发，⾛了 step 步之后，如果失败了。
            // 那么 [i, i + step] 这个区间内任意⼀个位置作为起点
            // 都不可能环绕⼀圈。
            i = i + step;
        }

        return -1;
    }
};

//单调递增的数字
class Solution
{
public:
    int monotoneIncreasingDigits(int n)
    {
        string s = to_string(n);
        for (int i = 0; i < s.size() - 1; i++)
        {
            // 找到第一个递减的位置
            if (s[i] > s[i + 1])
            {
                // 12345554处理这种情况
                int begin = i;
                while (begin >= 1 && s[begin] == s[begin - 1])
                    begin--;
                // 将其第一个递减的位置-1，其余后面的变为9
                s[begin]--;
                for (int j = begin + 1; j < s.size(); j++)
                    s[j] = '9';
                return stoi(s);
            }
        }
        return stoi(s);
    }
};

class Solution
{
public:
    int monotoneIncreasingDigits(int n)
    {
        string s = to_string(n);
        int i = 0, m = s.size();
        // 找第⼀个递减的位置
        while (i + 1 < m && s[i] <= s[i + 1]) i++;

        // 处理1234这种特殊情况
        if (i == m - 1) return n;

        // 12345554
        while (i - 1 >= 0 && s[i] == s[i - 1]) i--;
        s[i]--;

        for (int j = i + 1; j < m; j++) s[j] = '9';

        return stoi(s);
    }
};

//坏了的计算器
class Solution
{
public:
    int brokenCalc(int startValue, int target)
    {
        // 正难则反
        int ret = 0;
        while (target > startValue)
        {
            if (target % 2 == 0)
                target /= 2;
            else
                target++;
            ret++;
        }

        return ret + startValue - target;
    }
};

//合并区间
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        // 按照左端点从小到达排序
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ret;
        int n = intervals.size();
        // 合并区间
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 0; i < n; i++)
        {
            int a = intervals[i][0], b = intervals[i][1];
            // 有重叠的部分
            if (a <= right)
            {
                // 合并求并集
                left = min(left, a);
                right = max(b, right);
            }
            else
            {
                ret.push_back({ left,right });
                left = a;
                right = b;
            }
        }

        // 最后一个区间
        ret.push_back({ left,right });
        return ret;
    }
};
int main()
{
    return 0;
}